import { LinedListQueue } from 'data-structure/linkedList/LinkedListQueue'
import { LinkedListStack } from 'data-structure/linkedList/LinkedListStack'

// NOTE: 平衡二叉树(AVL) => 一种自平衡的二分搜索树
// 二分搜索树: 如果一个序列是顺序的, 且顺序添加到二叉树中, 那么二分搜索树将会退化为一个链表
// 平衡二叉树: 最大高度和最小高度之差不能超过 1
// 高度和节点数量之间的关系是 O(logn) 的特点

// 在 AVL 中的平衡二叉树定义: 对于任意的一个节点, 左子树和右子树的高度差不能超过 1,
// 与堆和线段树之中平衡二叉树定义不一样
// 标注节点的高度, 从而计算平衡因子(左右两个子树的高度差)
// 平衡因子: 左右两个子树的高度差

export interface MapTreeNodeInter<V = any> {
  key: number | string
  value: V
  left: AVLTreeNode<V> | null,
  right: AVLTreeNode<V> | null,
}

// 存在映射版本
export class AVLTreeNode<V = any> implements MapTreeNodeInter<V> {
  // interface
  public key!: number | string
  public value!: V
  public left: AVLTreeNode<V> | null = null
  public right: AVLTreeNode<V> | null = null
  public h: number = 1
  public count: number = 1
  // 该元素在那一层
  public depth: number = 0
  // 以该元素为根的树有多少个元素
  public size: number = 0
  constructor(key: number | string, value: V, left: AVLTreeNode<V>['left'] = null, right: AVLTreeNode<V>['right'] = null) {
    this.key = key
    this.value = value
    this.left = left
    this.right = right
  }
}

/**
 * 二分搜索树, 存储的数据必须要有可比较性
 * 1. 一个二叉树,
 * 2. 每一个节点的值: 大于其左子树的所有的值, 小于其右子树的所有的值
 * 3. 每一颗子树都是二分搜索树
 */
export class AVLTree<V = any> {

  private root!: AVLTreeNode<V>
  private size: number = 0
  constructor(root?: AVLTreeNode<V>) {
    this.root = root!
    if (root) {
      this.size = 1
    }
  }
  /**
 * getHeight: 获取一个节点高度
 */
  public getHeight(node: AVLTreeNode) {
    if (!node) {
      return 0
    }
    return node.h
  }

  /**
   * getBalanceFactor: 获取节点的平衡因子
   */
  public getBalanceFactor(node: AVLTreeNode<V>) {
    if (!node) {
      return 0
    }
    return this.getHeight(node.left!) - this.getHeight(node.right!)
  }

  /**
   * isEmpty
   */
  public isEmpty() {
    return this.size === 0
  }

  /**
   * floor: 寻找前驱
   */
  public floor() {
    // TODO: todo
  }

  /**
   * ceil: 寻找后继
   */
  public ceil() {
    // TODO: todo
  }

  /**
   * rank: 元素的排名
   */
  public rank() {
    // TODO: todo
  }

  /**
   * select: 根据排名来查找元素
   */
  public select() {
    // TODO: todo
  }

  /**
   * getRoot
   */
  public getRoot() {
    return this.root
  }

  /**
   * add
   */
  public add(newNode: AVLTreeNode<V>) {
    this.root = this.addNode(this.root, newNode)
  }

  /**
   * removeMaxNode: 删除最大值的节点
   */
  public removeMax(): AVLTreeNode<V> {
    let node = this.maximum()

    // 删除以 root 为根节点的树中删除 node
    this.root = this.removeMaxTreeNode(this.root)

    return node
  }

  /**
   * removeMinNode: 删除最小值的节点
   */
  public removeMin(): AVLTreeNode<V> {
    let node = this.minimum()

    // 删除以 root 为根节点的树中删除 node
    this.root = this.removeMinTreeNode(this.root)

    return node
  }

  /**
   * remove: 删除任意的元素
   */
  public remove(node: AVLTreeNode<V>) {
    this.root = this.removeTreeNode(this.root, node) as AVLTreeNode
  }

  /**
   * minimum: 查找最小元素
   */
  public minimum(): AVLTreeNode<V> {
    return this.minimunTree(this.root)
  }

  /**
   * maximum: 查找最大元素
   */
  public maximum(): AVLTreeNode<V> {
    return this.maximunTree(this.root)
  }

  /**
   * levelOrder: 层序遍历: (广度优先遍历: 更快的查找到对应的元素)
   */
  public levelOrder(cb: (node: AVLTreeNode<V> | null) => void) {
    const q = new LinedListQueue<AVLTreeNode<V>>()
    q.enqueue(this.root)
    while (!q.isEmpty()) {
      let cur = q.dequeue()
      cb(cur)
      if (cur.left) {
        q.enqueue(cur.left)
      }
      if (cur.right) {
        q.enqueue(cur.right)
      }
    }
  }

  /**
   * getSize
   */
  public getSize() {
    return this.size
  }

  /**
   * set: 更新节点的值
   */
  public set(key: number | string, value: V) {
    let node = this.query(key)
    if (node) {
      node.value = value
      return
    }
    this.add(new AVLTreeNode(key, value))
  }

  /**
   * get
   */
  public get(key: number | string): V | undefined {
    if (!this.root) {
      return undefined
    }
    const stack = new LinkedListStack<AVLTreeNode>()
    stack.push(this.root)
    while (!stack.isEmpty()) {
      let node = stack.pop()
      if (key === node.key) {
        return node.value
      }
      if (node.right) {
        stack.push(node.right)
      }
      if (node.left) {
        stack.push(node.left)
      }
    }
    return undefined
  }

  /**
   * query
   */
  public query(key: number | string): AVLTreeNode<V> | null {
    if (!this.root) {
      return null
    }
    const stack = new LinkedListStack<AVLTreeNode>()
    stack.push(this.root)
    while (!stack.isEmpty()) {
      let node = stack.pop()
      if (key === node.key) {
        return node
      }
      if (node.right) {
        stack.push(node.right)
      }
      if (node.left) {
        stack.push(node.left)
      }
    }
    return null
  }

  /**
   * isBST: 是否是一颗二叉树, 性质, 使用中序排序的时候是一个顺序的序列
   */
  public isBST(): boolean {
    let keys: string[] = []
    this.inOrderRecursion(keys)
    console.log(keys)
    let isBST = true
    for (let i = 1; i < keys.length; i++) {
      if (keys[i - 1] > keys[i]) {
        isBST = false
      }
    }
    return isBST
  }

  /**
   * isBalanced
   */
  public isBalanced() {
    return this.isBalancedTree(this.root)
  }

  /**
   *  preorder: 深度优先遍历[前序遍历(递归)];
   */
  public preOrderRecursion(cb: (node: AVLTreeNode<V> | null) => void) {
    this.preOrderTreeRecursion(this.root, cb)
  }

  /**
   * preorder: 非递归的实现
   */
  public preOrder(cb: (node: AVLTreeNode<V> | null) => void) {
    if (!this.root) {
      return
    }
    const stack = new LinkedListStack<AVLTreeNode>()
    stack.push(this.root)
    while (!stack.isEmpty()) {
      let node = stack.pop()
      cb(node)
      if (node.right) {
        stack.push(node.right)
      }
      if (node.left) {
        stack.push(node.left)
      }
    }
  }

  /**
   * inOrder: 深度优先遍历: [中序遍历(递归实现)] 得到的结果是一个有序的序列,
   */
  public inOrderRecursion(keys?: Array<string | number>) {
    this.inOrderTreeRecursion(this.root, keys)
  }

  /**
   * postOrderRecursion: 深度优先遍历: 后序遍历(递归实现)
   */
  public postOrderRecursion(cb: (node: AVLTreeNode<V> | null) => void) {
    this.postOrderTreeRecursion(this.root, cb)
  }

  /**
   * contains
   */
  public contains(key: string | number): boolean {
    return this.containsNode(this.root, key)
  }

  private isBalancedTree(node: AVLTreeNode): boolean {
    if (!node) {
      return true
    }
    let balanceFactor = this.getBalanceFactor(node)
    if (Math.abs(balanceFactor) > 1) {
      return false
    }
    return this.isBalancedTree(node.left!) && this.isBalancedTree(node.right!)
  }

  private removeTreeNode(node: AVLTreeNode<V>, delNode: AVLTreeNode<V>): AVLTreeNode<V> | null | void {
    // 没有该节点
    if (!node) {
      return null
    }
    let ret: AVLTreeNode<V>
    if (node.key > delNode.key) { // 在左子树
      node.left = this.removeTreeNode(node.left!, delNode) as AVLTreeNode
      ret = node
    } else if (node.key < delNode.key) { // 在右子树
      node.right = this.removeTreeNode(node.right!, delNode) as AVLTreeNode
      ret = node
    } else { // 找到了对应的节点
      this.size--
      if (!node.left) {
        let right = node.right
        node.right = null
        ret = right as AVLTreeNode<V>
      } else if (!node.right) {
        let left = node.left
        node.left = null
        ret = left as AVLTreeNode<V>
      } else {
        // 左右子树都存在的话, 需找到当前节点的后继中
        let min = this.minimunTree(node.right!)
        // 这里进行了 size--; 实际上这里是寻找子树的新的根节点
        min.right = this.removeTreeNode(node.right!, min) as AVLTreeNode<V>
        // 所以这里要 size++
        min.left = node.left
        node.left = node.right = null
        ret = min
      }
    }

    if (!ret) {
      return null
    }
    // 这里已经向上回溯到根节点
    // 无论是在左子树或者是右字数添加节点, 高度都会变化, 更新 height, 因为左右子树的高度之差小于等于 1
    ret = this.autoBalanced(ret)
    return ret
  }

  private autoBalanced(node: AVLTreeNode<V>) {
    node.h = 1 + Math.max(this.getHeight(node.right!), this.getHeight(node.left!))
    // 计算平衡因子
    let balanceFactor = this.getBalanceFactor(node)
    // 平衡维护
    if (balanceFactor > 1) {
      if (this.getBalanceFactor(node.left!) >= 0) { // LL 情况
        // 右旋转, 左边添加了一个节点从而高于右边,
        // 右旋转: 需找到失去平衡的根节点, 然后将该节点 的左子树节点的右孩子指向之前的 根节点, 然后将这右孩子变为根节点的左孩子
        return this.rightRotate(node)
      } else { // LR
        node.left = this.leftRotate(node.left!)
        return this.rightRotate(node)
      }
    } else if (balanceFactor < -1) {
      if (this.getBalanceFactor(node.right!) <= 0) { // 左旋转 RR 情况
        return this.leftRotate(node)
      } else { // RL
        node.right = this.rightRotate(node.right!)
        return this.leftRotate(node)
      }
    }
    return node
  }

  private removeMaxTreeNode(node: AVLTreeNode<V>): AVLTreeNode<V> {
    if (!node.right) {
      let left = node.left
      node.left = null
      this.size--
      return left!
    }
    node.right = this.removeMaxTreeNode(node.right)
    return node
  }

  // 删除: node, 放回删除节点后的新的树
  private removeMinTreeNode(node: AVLTreeNode<V>): AVLTreeNode<V> {
    if (!node.left) {
      let right = node.right
      node.right = null
      this.size--
      return right!
    }
    node.left = this.removeMinTreeNode(node.left)
    return node
  }

  private minimunTree(node: AVLTreeNode<V>): AVLTreeNode<V> {
    if (!node.left) {
      return node
    }
    return this.minimunTree(node.left)
  }

  private maximunTree(node: AVLTreeNode<V>): AVLTreeNode<V> {
    if (!node.right) {
      return node
    }
    return this.maximunTree(node.right)
  }

  private postOrderTreeRecursion(node: AVLTreeNode<V>, cb: (node: AVLTreeNode<V> | null) => void) {
    if (!node) {
      cb(null)
      return
    }
    this.postOrderTreeRecursion(node.left!, cb)
    this.postOrderTreeRecursion(node.right!, cb)
    cb(node)
  }

  private inOrderTreeRecursion(node: AVLTreeNode<V>, keys?: Array<string | number>) {
    if (!node) {
      return
    }

    this.inOrderTreeRecursion(node.left!, keys)
    if (keys) {
      keys.push(node.key)
    }
    this.inOrderTreeRecursion(node.right!, keys)
  }

  private preOrderTreeRecursion(node: AVLTreeNode<V>, cb: (node: AVLTreeNode<V> | null) => void) {
    if (!node) {
      return cb(null)
    }
    cb(node)
    this.preOrderTreeRecursion(node.left!, cb)
    this.preOrderTreeRecursion(node.right!, cb)
  }

  private containsNode(node: AVLTreeNode<V>, key: string | number): boolean {
    if (!node) {
      return false
    }
    if (node.key > key) { // 左子树
      return this.containsNode(node.left!, key)
    } else if (node.key < key) { // 右子树
      return this.containsNode(node.right!, key)
    }
    return true
  }

  /**
   * 右旋转:
   * LL 情况
   * @param y 对 y 节点进行右旋转
   *       y                                       x
   *      / \                                   /     \
   *     x   T4  (不平衡的节点 y, 进行右旋转)      z      y
   *    / \      ------------------------>    / \    /  \
   *   z   T3                                T1 T2  T3  T4
   *  / \
   * T1  T2
   *
   * x = y.left
   * right = x.right
   * x.right = y
   * y.left = right
   *
   * NOTE: LR
   *       y(-2)                           y                                z
   *      / \                            /  \                            /     \
   *     x  T1  左旋转(y.left)->(RR)     z   T1           左旋转          x       y
   *    / \     ------------------->   / \       ------------->        / \     /  \
   *   T2  z                          x  T4                           T3 T2   T4  T1
   *      / \                        / \
   *    T3  T4                     T3   T2
   */
  private rightRotate(y: AVLTreeNode<V>): AVLTreeNode<V> {
    let x = y.left as AVLTreeNode<V>
    let right = x!.right
    x!.right = y
    y.left = right

    // 更新 height

    y.h = Math.max(this.getHeight(y.left!), this.getHeight(y.right!)) + 1
    x.h = Math.max(this.getHeight(x.left!), this.getHeight(x.right!)) + 1
    return x
  }

  /**
   * 左旋转
   * NOTE: RR 情况
   * @param y 对 y 节点进行右旋转
   *       y                                        x
   *      / \                                    /     \
   *     T1   x    (不平衡的节点 y, 进行右旋转)     y      z
   *         / \    ------------------------>  / \    /  \
   *        T2   z                            T1 T2  T3  T4
   *            / \
   *          T3  T4
   *  x = y.right
   * left = x.left
   * x.left = y
   * y.right = left
   *
   * NOTE: RL
   *       y(-2)                            y                                z
   *      / \                             /  \                            /     \
   *     T1  x    右旋转(y.right)->(RR)  T1   z        左旋转             y       x
   *        / \   ------------------->      / \       ------------->  / \     /  \
   *       z  T2                           T3  x                     T1 T3   T4  T2
   *      / \                                 / \
   *    T3  T4                              T4  T2
   */
  private leftRotate(y: AVLTreeNode<V>): AVLTreeNode<V> {
    let x = y.right as AVLTreeNode<V>
    let left = x!.left
    x.left = y
    y.right = left

    // 更新 height, 由于 此时的 x, y 的左右子树发生了变化
    y.h = Math.max(this.getHeight(y.left!), this.getHeight(y.right!)) + 1
    x.h = Math.max(this.getHeight(x.left!), this.getHeight(x.right!)) + 1
    return x
  }

  // 向 node 为 根的二分搜索树添加节点
  // 放回插入新节点后二分搜索树的根
  private addNode(node: AVLTreeNode<V>, newNode: AVLTreeNode<V>): AVLTreeNode<V> {
    if (!node) {
      this.size++
      return newNode
    }
    if (node.key < newNode.key) { // 大于当前根节点
      node.right = this.addNode(node.right!, newNode)
    } else if (node.key > newNode.key) { // 小于
      node.left = this.addNode(node.left!, newNode)
    } else { // 等于
      node.value = newNode.value
    }

    // 这里已经向上回溯到根节点
    // 无论是在左子树或者是右字数添加节点, 高度都会变化, 更新 height, 因为左右子树的高度之差小于等于 1
    node = this.autoBalanced(node)
    return node
  }
}
